import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。

 * User: 86189
 * Date: 2022-02-14
 * Time: 17:44
 */
/*  思路：首先我们要知道无效字符串时什么样的：
     1、左括号多 : (((()、(({})
     2.右括号多  : )(()))、()))、{}([]))
     3.左右括号不匹配 : ({])、{](}
     4.左右括号没有以正确的顺序闭合 : {(}) 、 [{]}
     然后我们知道先出现的左括号应该由后出现的有括号闭合，后出现的左括号，应该由先出现的右括号闭合，这就刚好符合栈的特点
     想到栈的弹出是栈顶元素，所以我们想到把左括号都入栈，那么栈顶一直都是最近出现的左括号，而在遍历字符串的时候，应该由
     最近出现的右括号去闭合，当然在闭合这个过程中，我们必须要使得栈顶的左括号跟遍历的右括号是相同的类型才能闭合成功，
     如果有一个不匹配就会返回false,直到所有的括号都匹配成功才会返回true
*
* */
public class Solution {
    public static  boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        char[] chars=s.toCharArray();
        //是奇数长度肯定不匹配
        if(chars.length%2==1){
            return false;
        }
        for(int i = 0;i<chars.length;i++){
            //把所有左括号入栈
            if(chars[i]=='{' || chars[i] == '[' || chars[i] == '('){
                stack.push(chars[i]);
            }else{
                //如果栈为空，说明右括号多，返回fasle
                if(stack.isEmpty()){
                    return false;
                }
                //如果遇到右括号
                char top= stack.peek();//获取最近的左括号
                //看是否匹配类型
                if( top=='{' && chars[i] =='}' || top=='(' && chars[i] == ')' || top=='[' && chars[i] == ']'){
                    stack.pop(); //如果匹配了，那么就弹出栈顶的左括号，说明这个左括号匹配成功
                }else{
                    //不匹配类型
                    return  false;
                }
            }
        }
        //遍历完了字符串
        //如果栈不为空，说明有左括号没匹配完，返回fasle,正确的字符串遍历完，栈为空的时候，说明全部匹配完毕，返回true
        return stack.isEmpty(); //为空就返回true,说明是有效字符串

        //或者是利用哈希表来存储右括号与左括号的对应关系，栈存储左括号，当遍历到右括号的时候直接在哈希表中得到对应的左括号是否与栈顶的匹配
//        Map<Character,Character> map=new HashMap<>();
//        //当遍历到右括号时，看对应的左括号是不是和栈顶元素匹配
//        map.put('}','{');
//        map.put(']','[');
//        map.put(')','(');
//        //遍历字符串，看是否匹配
//        for (char aChar : chars) {
//            if (map.containsKey(aChar)) {
//                //包含了右括号，就要看是否和栈顶元素的左括号匹配
//                if (stack.isEmpty() || map.get(aChar) != stack.peek()) {
//                    return false; //不匹配返回false
//                }
//                //匹配成功就要弹出栈顶的左括号
//                stack.pop();
//            } else {
//                stack.push(aChar);
//            }
//        }
//        return  stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(isValid("{(}))]"));
    }
}
